package xyz.scootaloo.oj.leetcode

import cn.hutool.core.lang.Console
import org.junit.Test

/**
 * @author flutterdash@qq.com
 * @since 2021/4/21 23:10
 */
class P37 {

    fun solveSudoku(board: Array<CharArray>) {
        backtrack(board, 0, 0)
    }

    private fun backtrack(board: Array<CharArray>, row: Int, column: Int): Boolean {
        if (column == COLUMN) {
            return backtrack(board, row + 1, 0)
        }

        if (row == ROW) {
            return true
        }

        if (board[row][column] != '.') {
            return backtrack(board, row, column + 1)
        }

        for (ch in '1'..'9') {
            if (!isValid(board, row, column, ch))
                continue
            board[row][column] = ch
            if (backtrack(board, row, column + 1)) {
                return true
            }
            board[row][column] = '.'
        }

        return false
    }

    private fun isValid(board: Array<CharArray>, row: Int, column: Int, number: Char): Boolean {
        for (index in 0 until 9) {
            if (board[row][index] == number)
                return false
            if (board[index][column] == number)
                return false
            if (board[(row/3)*3 + index/3][(column/3)*3 + index%3] == number)
                return false
        }
        return true
    }

    companion object {
        const val ROW = 9
        const val COLUMN = 9
    }

    @Test
    fun test0() {
        val board = arrayOf(
            charArrayOf('5','3','.','.','7','.','.','.','.'),
            charArrayOf('6','.','.','1','9','5','.','.','.'),
            charArrayOf('.','9','8','.','.','.','.','6','.'),
            charArrayOf('8','.','.','.','6','.','.','.','3'),
            charArrayOf('4','.','.','8','.','3','.','.','1'),
            charArrayOf('7','.','.','.','2','.','.','.','6'),
            charArrayOf('.','6','.','.','.','.','2','8','.'),
            charArrayOf('.','.','.','4','1','9','.','.','5'),
            charArrayOf('.','.','.','.','8','.','.','7','9')
        )
        solveSudoku(board)
        val target = arrayOf(
            charArrayOf('5','3','4','6','7','8','9','1','2'),
            charArrayOf('6','7','2','1','9','5','3','4','8'),
            charArrayOf('1','9','8','3','4','2','5','6','7'),
            charArrayOf('8','5','9','7','6','1','4','2','3'),
            charArrayOf('4','2','6','8','5','3','7','9','1'),
            charArrayOf('7','1','3','9','2','4','8','5','6'),
            charArrayOf('9','6','1','5','3','7','2','8','4'),
            charArrayOf('2','8','7','4','1','9','6','3','5'),
            charArrayOf('3','4','5','2','8','6','1','7','9')
        )
        match(board, target)
    }

    private fun match(boardA: Array<CharArray>, boardB: Array<CharArray>) {
        showBoard(boardA)
        println("------------------")
        showBoard(boardB)
        for (r in 0 until ROW) {
            for (c in 0 until COLUMN) {
                if (boardA[r][c] != boardB[r][c])
                    throw Exception("错误 $r:$c")
            }
        }
    }

    private fun showBoard(board: Array<CharArray>) {
        for (line in board) {
            println(line.contentToString())
            Console.log()
        }
    }

}
